W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
We are given a rectangular city map comprising squares ( and ). The rows of squares of the map are numbered successively from top to bottom by numbers from to , and the columns from left to right successively from to . Each square is either free or blocked. Vehicular traffic is allowed only on free squares. From each free square one may move to a free square adjacent to it (i.e. a square that shares a side with it), however one is not allowed to turn back, i.e. to go back to a square immediately after moving from to an adjacent square .
The Right-Turn Drivers' Club ordered a computer program, which for any two different squares and decides whether it is possible to drive from to without turning left, and if so, the program finds such a route with the minimal length. The length of a route is the number of all its squares. The squares and are also considered squares of the route from to .
Write a program that:
In the first line of the standard input there are two integers separated by a single space: the number of rows and the number of columns . In each of the following lines of the file there is a description of the corresponding row of the map. Such a description has a form of one word of length consisting of digits and . The digit means that the corresponding square is free, and the digit that it is blocked.
Next, in one line, there are two coordinates of the square , separated by a single space: the row number not greater than and the column number not greater than . In the following line there are two coordinates of the square , written the same way.
The data in the standard input are written correctly and your program need not verify that.
The following should be written in the standard output:
For the input data:
8 9 010011101 011010101 000000000 111010101 101000100 111010101 000000000 101011111 2 6 1 3
the correct result is:
NIE
For the input data:
8 9 010011101 011010101 000000000 111010101 101000100 111010101 000000000 101011111 2 6 3 8
the correct result is:
12 2 6 3 6 4 6 5 6 5 5 5 4 4 4 3 4 3 5 3 6 3 7 3 8
Task author: Piotr Chrzastowski-Wachtel.